Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Databases are increasingly used in modern computing systems as demand for high-throughput databases coincides with the explosion of mobile computing, cloud computing, as well as many desktop applications. These forces have rapidly driven usage, size, and importance of database systems as critical server applications.
In many databases, B+ trees may be used as indexes in databases. For example, a B+ tree may contain many keys, each of which points to a set of records in the database. B+ trees offer efficient retrieval of stored values, especially in systems with large numbers of records. However, existing techniques for retrieving values from B+ trees and for modifying the trees may not efficiently take advantage of modern parallel processing techniques and/or capabilities.
One common approach to parallel processing of B+ trees in database indexes may use separately-executing threads that each asynchronously processes a single query. However, asynchronous techniques may require latches (e.g. control over in-memory resources to prevent threads from accessing the same data) for modify operations. Additionally, asynchronous techniques may present varying needs for retrieval operations. For example, some asynchronous techniques may use differing classes of latches for retrieval and modify operations, while other asynchronous techniques may not restrict retrieval operations. In both cases, many such methods may suffer performance penalties from the use of latches, reducing the utility of parallel processing on B+ trees.